Factorial trailing zeroes

Time: O(LogN)=O(1); Space: O(1); easy

Given an integer n, return the number of trailing zeroes in n!.

Example 1:

Input: n = 3

Output: 0

Explanation:

• 3! = 6, no trailing zero.

Example 2:

Input: n = 5

Output: 1

Explanation:

• 5! = 120, one trailing zero.

Note:

• Your solution should be in logarithmic time complexity.

class Solution1(object):
    def trailingZeroes(self, n) -> int:
        """
        :type n: int
        :rtype: int
        """
        result = 0
        while n > 0:
            result += n // 5
            n //= 5
        return result

s = Solution1()
n = 3
assert s.trailingZeroes(n) == 0
n = 5
assert s.trailingZeroes(n) == 1
n = 10
assert s.trailingZeroes(n) == 2
n = 100
assert s.trailingZeroes(n) == 24

See also:

https://leetcode.com/problems/factorial-trailing-zeroes

https://www.lintcode.com/problem/factorial-trailing-zeroes